package 蓝桥杯算法;

import 二叉树.TreeNode;

import java.util.Stack;

public class day21 {
    public static void main(String[] args) {

    }
    public TreeNode mergeTree(TreeNode root1,TreeNode root2){
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        root1.val+= root2.val;//此时已经加上了值
        root1.left=mergeTree(root1.left,root2.left);
        root1.right=mergeTree(root1.right,root2.right);
        return root1;
    }
    public TreeNode mergeTree2(TreeNode root1,TreeNode root2){
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root2);
        stack.push(root1);
        while (!stack.isEmpty()){
            TreeNode node1=stack.pop();
            TreeNode node2=stack.pop();
            node1.val+=node2.val;
            if(node1.right!=null&&node2.right!=null){
                stack.push(node2.right);
                stack.push(node1.right);
            }
            else{
                if(node1.right==null){
                    node1.right=node2.right;
                }
            }
            if(node2.left!=null&&node1.left!=null){
                stack.push(node2.left);
                stack.push(node1.left);
            }
            else {
                if(node1.left==null){
                    node1.left=node2.left;
                }
            }
        }
        return root1;
    }
    public TreeNode findNode(TreeNode root,int val){
       if(root==null||root.val==val){
           return root;
       }
      if(root.val>val){
           return findNode(root.left,val);
      }
      else {
          return  findNode(root.right,val);
      }
    }

}
